package match_string

import (
	"math"
	"math/big"
)

const size = 256

func BruteForce(parent, son string) bool {
	m := len(son)
	for i := range parent {
		if m+i <= len(parent) && parent[i:m+i] == son {
			return true
		}
	}
	return false
}

func RabinKarp(parent, son string) bool {
	m := len(son)
	base := uint64(26)
	values := make([]uint64, len(parent))
	hashString := func(s string) uint64 {
		hash := uint64(0)
		for i, v := range s {
			h := values[len(s)-i]
			if h == 0 {
				values[len(s)-i] = ExpOther(base, uint64(int64(len(s)-i)))
				h = values[len(s)-i]
			}
			hash += h * uint64(v)
		}
		return hash
	}
	sonHash := hashString(son)
	for i := range parent {
		if m+i <= len(parent) {
			subString := parent[i : m+i]
			if hashString(subString) == sonHash && son == subString {
				return true
			}
		}
	}
	return false
}

func ExpOther(base, exp uint64) uint64 {
	return uint64(math.Pow(float64(base), float64(exp)))
}

func Exp(base, exp *big.Int) uint64 {
	result := big.NewInt(1)
	return (result.Exp(base, exp, nil)).Uint64()
}

func BoyerMoore(text, pattern string) int {
	max := func(a, b int) int {
		if a < b {
			return b
		}
		return a
	}

	bc := PreBmBc(pattern)
	suffix, prefix := PreGs(pattern)
	n, m := len(text), len(pattern)
	i := 0
	// 当i == n-m时，此时son字符串最后一位恰好与parent字符串对齐
	for i <= n-m {
		var j int
		// 从后往前匹配
		for j = m - 1; j >= 0; j-- {
			// 此处是i+j,举例:
			// parent = abcdefg
			// son =     bcd
			// 当j = m - 1 = 3 -1 =2时，即d的下标，此时d对齐的是parent中的d，即下标3，此时i = 1,因为son的第一个字符与parent的第i个字符对齐，此时i = 1
			// 因此这里parent是i + j
			if text[i+j] != pattern[j] {
				break
			}
		}
		if j < 0 {
			return i
		}
		// 此时移动si - xi的距离，si即坏字符对应的模式串中的字符下标，xi即坏字符在模式串的下标，si = j,xi的下标，首先获取xi下标对应的值，即parent[i+j],然后从bc
		// 中获取下标，即bc[parent[i+j]]
		//i += j - bc[text[i+j]]

		bm := j - bc[text[i+j]]
		var gm int
		// 因为J是从m-1开始移动的，如果j < m-1，说明末尾有匹配的字符，即存在好后缀
		if j < m-1 {
			gm = moveByGS(j, m, suffix, prefix)
		}
		i += max(bm, gm)
	}
	return -1
}

func moveByGS(j, m int, suffix []int, prefix []bool) int {
	// 好后缀的长度
	k := m - 1 - j
	if val := suffix[k]; val != -1 {
		return j + 1 - val
	}
	// 寻找是否有与好后缀部分匹配的子串，j代表坏字符串，j +1 代表好后缀的开始，j+2代表好后缀子串的第一个下标，m-r代表子串的长度
	for r := j + 2; r <= m-1; r++ {
		if prefix[m-r] {
			return r
		}
	}
	return m
}

func PreBmBc(pattern string) []int {
	result := make([]int, 256)
	for i := range result {
		result[i] = -1
	}

	for i, v := range pattern {
		result[v] = i
	}
	return result
}

func PreGs(pattern string) ([]int, []bool) {
	m := len(pattern)
	suffix, prefix := make([]int, m), make([]bool, m)
	for i := range suffix {
		suffix[i] = -1
	}

	for i, v := range pattern {
		j, k := i, 0
		// 求公共后缀子串长度
		// 倒着比，在模式串中寻找是否有相匹配的子串
		for j >= 0 && v == int32(pattern[m-1-k]) {
			k++
			suffix[k] = j
			j--
		}
		// 长度为k的后缀子串在前缀子串中有完全匹配的地方
		if j == -1 {
			prefix[k] = true
		}
	}
	return suffix, prefix
}

func KnuthMorrisPratt(text, pattern string) int {
	next := getNext(pattern)
	var j int
	for i := 0; i < len(text); i++ {
		for j > 0 && text[i] != pattern[j] {
			j = next[j-1] + 1
		}

		if text[i] == pattern[j] {
			j++
		}

		// 这里是j == len(pattern)，因为在text[i] == pattern[j] 比较之后j才进行++操作，此时j的值并未比较，所以不能是j == len(pattern) - 1的时候返回
		if j == len(pattern) {
			return i - len(pattern) + 1
		}
	}
	return -1
}

func getNext(pattern string) []int {
	result := make([]int, len(pattern))
	result[0] = -1
	k := -1 //这里初始化为-1,是因为我们返回数组记录的是下标而非长度，如果不存在，下标计为-1

	// i代表后缀子串的末尾，k + 1代表前缀子串的末尾
	for i := 0; i < len(pattern); i++ {
		if pattern[i] == pattern[k+1] {
			k++
		}

		if k > -1 && pattern[i] != pattern[k+1] {
			k = result[k]
		}
		result[i] = k
	}
	return result
}
